import java.util.Arrays;

class BST {
    Node root;

    public BST(int[] keys) {
        Arrays.sort(keys);
        int mid = (keys.length - 1) / 2;
        this.root = new Node(keys[mid]);
        build_bst(keys, root, 0, mid);
        build_bst(keys, root, mid + 1, keys.length - 1);
    }

    private void build_bst(int[] keys, Node parentNode, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        Node currentNode = new Node(keys[mid]);
        if (keys[mid] < parentNode.key) {
            go_left(currentNode, parentNode);
        } else if (keys[mid] > parentNode.key) {
            go_right(currentNode, parentNode);
        }
        build_bst(keys, currentNode, left, mid);
        build_bst(keys, currentNode, mid + 1, right);
    }

    private void go_right(Node currentNode, Node parentNode) {
        parentNode.right_child = currentNode;
        currentNode.parent = parentNode;
    }

    private void go_left(Node currentNode, Node parentNode) {
        parentNode.left_child = currentNode;
        currentNode.parent = parentNode;
    }

    public Integer predecessor(int q) {
        Node currentNode = findNode(q);
        if (currentNode == null)
            System.out.println("key not exist!");
        else {
            if (currentNode.left_child != null)
                return findMax(currentNode);
            else {
                Node p = currentNode.parent;
                Node t = currentNode;
                while (p != null && t == p.left_child) {
                    t = p;
                    p = t.parent;
                }
                if (p != null)
                    return p.key;
            }
        }
        return -1;
    }

    private int findMax(Node node) {
        Node currentNode = node;
        while (!(isLeaf(currentNode))) {
            currentNode = currentNode.right_child;
        }
        return currentNode.key;
    }

    private Node findNode(int value) {
        return find_recursive(root, value);
    }

    private Node find_recursive(Node currentNode, int key) {
        if (currentNode == null || currentNode.key == key)
            return currentNode;
        if (currentNode.key > key) {
            return find_recursive(currentNode.left_child, key);
        }
        return find_recursive(currentNode.right_child, key);
    }

    private boolean isLeaf(Node currentNode) {
        return currentNode.left_child == null && currentNode.right_child == null;
    }

    public void print(Node root, int k) {
        if (root != null) {
            print(root.right_child, k + 5);
            for (int i = 0; i < k; i++) {
                System.out.print(" ");
            }
            System.out.println(root.key);
            print(root.left_child, k + 5);
        }

    }

    static class Node {
        int key;
        Node parent;
        Node left_child;
        Node right_child;

        public Node(int data) {
            key = data;
            left_child = null;
            right_child = null;
            parent = null;
        }
    }
}

class test {
    public static void main(String[] args) {
        int[] keys = {46, 5, 24, 14, 78, 9, 63, 53, 7};
        BST bst = new BST(keys);
        System.out.println("rotate 90 degrees to make it a bst ^ ^");
        bst.print(bst.root, 0);
        System.out.println("predecessor of the smallest number: " + bst.predecessor(5));
        System.out.println("predecessor of other numbers: (like 63): " + bst.predecessor(63));
    }
}